import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-03 22:53
 */
public class QuickSort {

    public static int THREASHOLD = 16;

    public static void main(String[] args) {
        double[] array1 = new double[]{45, 34, 78, 12, 34, 32, 29, 64};
        double[] array2 = new double[]{25, 34, 45, 32, 34, 12, 29, 64};
        double[] array3 = new double[]{45, 34, 78, 12, 34, 32, 29, 64};
//        quickSort(array1, 0, array1.length-1);
//        System.out.println(Arrays.toString(array1));
        quickSortT(array2, 0, array2.length-1);
        System.out.println(Arrays.toString(array2));
        quickSortTPro(array3, 0, array3.length-1);
        System.out.println(Arrays.toString(array3));
    }

    public static void quickSort(double[] array, int begin, int end){
        if(begin<end){
            int pivot = partition(array, begin, end);
            quickSort(array, begin, pivot-1);
            quickSort(array, pivot+1, end);
        }
    }

    public static int partition(double[] array, int begin, int end){
        int i = begin;
        int j = end;
        while(i<j){
            while(i<j && array[i]<=array[j]){
                i++;
            }
            if(i<j){
                swap(array, i, j);
                j--;
            }
            while(i<j && array[i]<=array[j]){
                j--;
            }
            if(i<j){
                swap(array, i, j);
                i++;
            }
        }
        return i;
    }

    public static void quickSortT(double[] array, int start, int end){
        if(end<=start) return;
        int pivot = selectPivotT(start, end);
        swap(array, pivot, end);
        pivot = partitionT(array, start, end);
        quickSortT(array, start, pivot-1);
        quickSortT(array, pivot+1, end);
    }

    public static int selectPivotT( int start, int end){
        return (start+end)/2;
    }

    public static int partitionT( double[] array, int start, int end){
        double tempElem = array[end];
        int i = start;
        int j = end;
        while(i!=j){
            while(array[i]<tempElem && (i<j)){
                i++;
            }
            if(i<j){
                array[j] = array[i];
                j--;
            }
            while(array[j]>tempElem && i<j){
                j--;
            }
            if(i<j){
                array[i] = array[j];
                i++;
            }
        }
        array[i] = tempElem;
        return i;
    }

    public static void quickSortTPro(double[] array, int start, int end){
        doSortTPro(array, start, end);
        InsertionSort.insertionSort(array);
    }

    public static void doSortTPro(double[] array, int start, int end){
        if(end<=start || end-start+1<THREASHOLD) return;
        int pivot = selectPivotT(start, end);
        swap(array, pivot, end);
        pivot = partitionT(array, start, end);
        quickSortT(array, start, pivot-1);
        quickSortT(array, pivot+1, end);
    }

    public static void swap(double[] array, int indexi, int indexj){
        double temp = array[indexi];
        array[indexi] = array[indexj];
        array[indexj] = temp;
    }
}
